<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>将数组分成两个数组并最小化数组和的差</title>
</head>
<body>
  <script>
    function fn(nums) {
      let total = nums.reduce((total, item) => total + item, 0);
      let n = nums.length / 2;

      let leftArr = nums.slice(0, n);
      let rightArr = nums.slice(n);
      // 根据当前怎么选的feature 去集合setArr里找 选中的数  并求和
      function getSum(feature, setArr) {
        let ret = 0;
        // 可能在哪些位会出现1
        for (let i = 0; i < n; i++) {
          // 当前位选了
          if (feature & (1 << i)) {
            ret += setArr[i];
          }
        }
        return ret;
      }

      // key 左边1的个数 或者说左边选了几个数  可能0~15个
      // value 选了key对应个数时  可能组成的数字和有哪些
      let leftMap = new Array(n + 1);
      // leftMap[0] = [0];
      // 同理
      let rightMap = new Array(n + 1);
      // rightMap[0] = [0];

      // 获取1的个数
      function getOneNum(num) {
        let ret = 0;
        while (num) {
          let tmp = num & -num;
          num ^= tmp;
          ret++;
        }
        return ret;
      }
      for (let i = 0; i < 2 ** n; i++) {
        let oneNum = getOneNum(i);
        leftMap[oneNum] = leftMap[oneNum] || [];
        rightMap[oneNum] = rightMap[oneNum] || [];
        leftMap[oneNum].push(getSum(i, leftArr));
        rightMap[oneNum].push(getSum(i, rightArr));
      }
      let target = total / 2;
      // 排个序二分..
      for (let i = 0; i <= n; i++) {
        leftMap[i] = leftMap[i].sort((a, b) => a - b);
        // leftMap[i] = [...new Set(leftMap[i])];
        rightMap[i] = rightMap[i].sort((a, b) => a - b);
        // rightMap[i] = [...new Set(rightMap[i])];
      }
      function findRecent(arr, target) {
        let l = 0;
        let r = arr.length - 1;
        // 这里本质也是个能力二分..  找到恰好比target大的最小index （满足xxxx的最小index）
        while (l < r) {
          let middle = (l + r) >> 1;
          if (arr[middle] == target) {
            return target;
          } else if (arr[middle] > target) {
            r = middle;
          } else {
            l = middle + 1;
          }
        }
        if (l == 0) {
          return arr[l];
        }
        let left = Math.abs(arr[l - 1] - target);
        let right = Math.abs(arr[l] - target);
        if (left < right) {
          return arr[l - 1];
        } else {
          return arr[l];
        }
      }
      let ret = Infinity;
      // 左边拿i个数
      for (let i = 0; i <= n; i++) {
        // 这时候题就变成找波谷了.. 你理解一下  可能有点突兀  当然也可能没波谷 那就找最低点
        for (let j = 0; j < leftMap[i].length; j++) {
          let now = leftMap[i][j];
          // 二分找最理想的那个值
          now += findRecent(rightMap[n - i], target - now);
          let other = total - now;
          ret = Math.min(ret, Math.abs(now - other));
        }

      }
      return ret;
    }
    console.log(fn([3, 9, 7, 3]))
  </script>
</body>
</html>